#ifndef GRAPH_H_
#define GRAPH_H_

#include <vector>
#include <stack>
#include <list>
#include "GraphNode.h"
#include "GraphEdge.h"

typedef std::vector<GraphNode> vNodes;
typedef std::list<GraphEdge> lEdge;
typedef std::vector<lEdge> vEdgeList;

/* Path finding class. Wrapped by the Grid class, although it can
   be used on is own manually. 
*/
class Graph
{
public:
    friend class Grid;
public:
    Graph() : m_index(0) {}

    int AddNode(GraphNode& node)
    {
        if(node.GetID() < m_index)//this node has been removed, so add it back in
        {
            m_nodes[node.GetID()] = node;
            return m_index;
        }
        else//this is a new node, add it in and create a list of edges for it
        {
            m_nodes.push_back(node);
            m_listEdges.push_back(lEdge());
            return m_index++;
        }
    }
    /* Currently, we can remove nodes dynamically, but we can't 
       add them back in!
    */
    void RemoveNode(int id)
    {
        //first, get a list of all the edges going from this node
        lEdge edgeList = m_listEdges[id];
        for(lEdge::iterator it = edgeList.begin(); 
            it != edgeList.end(); ++it)
        {
            GraphNode n = m_nodes[it->To()];
            //then, for each of the edges, get the node at the end,
            for(lEdge::iterator remove = m_listEdges[n.GetID()].begin(); 
                remove != m_listEdges[n.GetID()].end();
                ++remove)
            {
                if(remove->To() == id)
                {
                    remove = m_listEdges[n.GetID()].erase(remove);
                    break;
                }
            }
        }
        m_nodes[id].SetId(-1);
        m_listEdges[id].clear();
    }
    void AddEdge(GraphEdge& edge)
    {
        if (IsValid(edge))
        {
            if(!EdgeExists(edge.From(), edge.To()))
                m_listEdges[ edge.From()].push_back(edge);
            if(!EdgeExists(edge.To(), edge.From()))
            {
                GraphEdge e;
                e.From(edge.To());
                e.To(edge.From());
                e.Cost(edge.Cost());
                m_listEdges[ e.From()].push_back(e);
            }
        }
    }
    bool EdgeExists(int from, int to)
    {
        lEdge::iterator it = m_listEdges[from].begin();
        for(; it != m_listEdges[from].end(); ++it)
            if(it->To() == to)
                return true;
        return false;
    }
    bool IsValid(GraphEdge& edge)
    {
        if(edge.From() > m_index || edge.To() > m_index)
            return false;
        if(edge.From() == -1 || edge.To() == -1)
            return false;
        if(edge.From() == edge.To())
            return false;
        if(m_nodes[edge.From()].GetID() == -1 ||
            m_nodes[edge.From()].GetID()== -1 )
           return false;

        return true;
    }
    void Clear() {m_nodes.empty();m_listEdges.empty();}
    const vEdgeList& ListEdges() const{ return m_listEdges; }
    const vNodes& Nodes() const{return m_nodes;}
    int GetCurrentIndex() const {return m_index;}
private:
    vNodes m_nodes;
    vEdgeList m_listEdges;
    int m_index;
};
#endif